package Harmonisation.CreationDuChant.Arbre;

import java.util.ArrayList;
import java.util.Iterator;
import Exception.ArbreCheminBloqueException;

public class Arbre<T> {
	private ArrayList<ArrayList<Noeud<T>>> enchainement;

	public Arbre() {
		this.enchainement = new ArrayList<ArrayList<Noeud<T>>>();
	}

	public int tailleArbre() {
		return enchainement.size();
	}

	public ArrayList<Noeud<T>> obtenirElement(int indice) {
		ArrayList<Noeud<T>> list = null;
		if (this.enchainement.size() > indice) {
			list = this.enchainement.get(indice);
		}
		return list;
	}

	public ArrayList<Noeud<T>> obtenirDernierElement() {
		ArrayList<Noeud<T>> list = null;
		if (!this.enchainement.isEmpty()) {
			list = this.enchainement.get(this.enchainement.size() - 1);
		}
		return list;
	}

	public int size() {
		return this.enchainement.size();
	}

	public void enleverCheminBloque() throws ArbreCheminBloqueException {
		ArrayList<Noeud<T>> listOublie = new ArrayList<Noeud<T>>();
		if (this.enchainement.size() >= 2) {
			ArrayList<Noeud<T>> noeudArbre = this.enchainement.get(this.enchainement.size() - 2);
			// System.out.println("On analyse dans cheminbloque l'array "+noeudArbre);
			Iterator<Noeud<T>> it = noeudArbre.iterator();
			while (it.hasNext()) {
				Noeud<T> noeud = it.next();
				if (noeud.getSuivant().size() == 0) {
					// System.out.println("On entre dans oublier pour " + noeud);

					oublier(noeud, this.enchainement.size() - 2);
					listOublie.add(noeud);
				}
			}
			oublierElementsDUneList(listOublie, this.enchainement.get(this.enchainement.size() - 2));
		}

	}

	public void oublier(Noeud<T> noeud, int arrayListContenante) throws ArbreCheminBloqueException {/*
																									 * on oublie le noeud, il faut donc regarder ensuite si ses predecesseur
																									 * doivent etre oublié ou non
																									 */
		ArrayList<Noeud<T>> listOublie = new ArrayList<Noeud<T>>();

		if (arrayListContenante != 0) {
			Iterator<Noeud<T>> it = this.enchainement.get(arrayListContenante - 1).iterator();
			while (it.hasNext()) {
				Noeud<T> noeudParent = it.next();
				if (noeudParent.getSuivant().contains(noeud)) {

					noeudParent.getSuivant().remove(noeud);
					if (noeudParent.getSuivant().size() == 0) {
						if (arrayListContenante - 1 != 0) {
							oublier(noeudParent, arrayListContenante - 1);
						}
						listOublie.add(noeudParent);
					}
				}
			}

			oublierElementsDUneList(listOublie, this.enchainement.get(arrayListContenante - 1));
		}

	}

	public void oublierElementsDUneList(ArrayList<Noeud<T>> aSupprimer, ArrayList<Noeud<T>> list) throws ArbreCheminBloqueException {
		/* la levee d'exception java.util.ConcurrentModificationException nous oblige a proceder avec une liste de noeud a oublier */
		Iterator<Noeud<T>> it = aSupprimer.iterator();
		while (it.hasNext()) {

			Noeud<T> noeud = it.next();
			list.remove(noeud);

		}
		if (list.size() == 0)/* il ne faut jamais qu'il y'ai un arraylist<arraylist<noeud> vide a part le dernier */
		{
			throw new ArbreCheminBloqueException("Aucun chemin");
		}
	}

	public void ajouter(ArrayList<Noeud<T>> arrayListNoeud) throws ArbreCheminBloqueException {
		this.enchainement.add(arrayListNoeud);
		enleverCheminBloque();
	}

	public String toString() {
		String s = "";
		Iterator<ArrayList<Noeud<T>>> it = enchainement.iterator();
		while (it.hasNext()) {
			s += "{" + it.next() + "}\n";
		}
		return s;
	}

	public ArrayList<T> genererCheminAleatoire() {
		ArrayList<T> chemin = new ArrayList<T>();
		if (!this.enchainement.isEmpty()) {
			/*
			 * on prend un premier noeud dans la 1er arraylist de l'abre, puis
			 * on suit les voisins de ce noeuds tant que le nombre de voisin du
			 * noeud!=0
			 */
			ArrayList<Noeud<T>> array = this.enchainement.get(0);
			int random = (int) (Math.random() * (array.size() - 0)) + 0;
			Noeud<T> noeud = array.get(random);
			chemin.add(noeud.getElement());
			/* on ajoute maintenant les suivants */

			do {

				noeud = voisinSuivantAleatoire(noeud);
				if (noeud != null) {
					chemin.add(noeud.getElement());
				}
			} while (noeud != null);
		}
		return chemin;
	}

	public Noeud<T> voisinSuivantAleatoire(Noeud<T> noeud) {

		ArrayList<Noeud<T>> arrayVoisin = noeud.getSuivant();
		if (arrayVoisin.size() == 0) {

			return null;
		}
		int random = (int) (Math.random() * (arrayVoisin.size() - 0)) + 0;

		return arrayVoisin.get(random);
	}

}
